#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool dfs(vector<vector<char>>& grid, vector<vector<vector<bool>>>& dp, int x, int y, int c, int n, int m) {
        if (c > n - x + m - y - 1) return false;
        if (x == n - 1 && y == m - 1) return c == 1;
        if (dp[x][y][c]) return false;
        dp[x][y][c] = true;
        c += grid[x][y] == '(' ? 1 : -1;
        if (c == -1) return false;
        return (x + 1 < n && dfs(grid, dp, x + 1, y, c, n, m)) || (y + 1 < m && dfs(grid, dp, x, y + 1, c, n, m));
    }
    bool hasValidPath(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[n - 1][m - 1] == '(') return false;
        vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(m, vector<bool>((n + m + 1) / 2)));
        return dfs(grid, dp, 0, 0, 0, n, m);
    }
};